package com.lun.swordtowardoffer2.c07;

import java.util.LinkedList;
import java.util.Queue;

import com.lun.util.BinaryTree.TreeNode;

public class FindBottomLeftValue {

	public int findBottomLeftValue(TreeNode root) {
		Queue<TreeNode> queue1 = new LinkedList<>();
		Queue<TreeNode> queue2 = new LinkedList<>();
		boolean queue1Flag = true;
		int bottomLeft = root.val;
		Queue<TreeNode> currentQueue = null;
		
		queue1.offer(root);
		currentQueue = queue1;
		
		while(!currentQueue.isEmpty()) {
			TreeNode node = currentQueue.poll();
			
			Queue<TreeNode> nextQueue = queue1Flag ? queue2 : queue1;
			if(node.left != null) {
				nextQueue.offer(node.left);
			}
			
			if(node.right != null) {
				nextQueue.offer(node.right);
			}
			
			if(currentQueue.isEmpty()) {
				currentQueue = nextQueue;
				queue1Flag = !queue1Flag;
				
				if(!currentQueue.isEmpty()) {
					bottomLeft = currentQueue.peek().val;
				}
			}
		}
		
		return bottomLeft;
	}
	
}
